#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 19;
int S[] = {2,3,5,7,11,13,17,23,31,37,53,71,73,113,131,137,173,311,317};

int main() {
    int T;
    cin>>T;
    string s;
    for (int cas=1; cas<=T; ++cas) {
        cin>>s;
        if (s.length()>3) {
            printf("Case #%d: %d\n", cas, 317);
        }
        else {
            int ask = 0;
            int len = s.length();
            for (int i=0; i<len; ++i) {
                ask = ask * 10 + s[i] - '0';
            }
            int it=0;
            while (it<N && S[it] <= ask) ++it;
            --it;
            printf("Case #%d: %d\n", cas, S[it]);
        }
    }
    return 0;
}
